// Copyright (C) 2012 Yury Bychenkov (http://bychenkov.com).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//  - Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//  - Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//  - Neither the name of Yury Bychenkov nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "numberutil.h"
#include <string.h>

inline bool IndexBuilder::add(uint32 value) {
	if (count == capacity) {
		if (!buildChunk()) {
			return false;
		}
	}
    
	values[count++] = value;

	return true;
}

inline Index::Index(const uint8* data_, uint dataSize_, uint chunkSize_):
	data(data_),
	chunkSize(chunkSize_),
	chunkCount(dataSize_ / chunkSize)
{
}

inline typename Index::Iterator Index::iterator(uint32 rangeMin, uint32 rangeMax) const {
	return Iterator(*this, rangeMin, rangeMax);
}

inline Index::Iterator& Index::Iterator::operator=(const Index::Iterator& that) {
	chunkSize = that.chunkSize;
	header = that.header;
	remainingChunkCount = that.remainingChunkCount;
	rangeMin = that.rangeMin;
	rangeMax = that.rangeMax;

	payload = that.payload;
	bitCount = that.bitCount;
	baseValue = that.baseValue;

	bits = that.bits;
	availableBits = that.availableBits;

	remainingCount = that.remainingCount;

	valueIndex = that.valueIndex;
	value = that.value;

	return *this;
}

inline Index::Iterator::Iterator():
	remainingCount(0)
{
}

inline Index::Iterator::Iterator(const Index& index, uint32 rangeMin_, uint32 rangeMax_):
	chunkSize(index.chunkSize),
	header((Header*) index.data),
	remainingChunkCount(index.chunkCount),
	rangeMin(rangeMin_),
	rangeMax(rangeMax_),
	remainingCount(1),
	valueIndex(0)
{
}

inline uint Index::Iterator::getValueIndex() const {
	return valueIndex;
}

inline uint32 Index::Iterator::getValue() const {
	return value;
}

inline bool Index::Iterator::nextChunk() {
	while (remainingChunkCount > 0) {
		const Header* h = header;
		
		header = (const Header*) (((const uint8*) header) + chunkSize);
		remainingChunkCount--;

		if (rangeMax < h->minValue || h->maxValue < rangeMin) {
			valueIndex += h->count;
			continue;
		}
	
		payload = (const uint64*)(((const uint8*) h) + sizeof(Header));
		bitCount = h->bitCount;
		baseValue = h->minValue;
		remainingCount = h->count;
		availableBits = 0;
	
		return true;
	}
	
	return false;
}

inline void Index::Iterator::fetchValue() {
    const uint64 bitMask = (1ULL << bitCount) - 1;

	if (availableBits >= bitCount) {
		value = uint32(bits & bitMask) + baseValue;

		bits >>= bitCount;
		availableBits -= bitCount;
	} else {
		uint64 b = bits;
		bits = *payload++;
	    value = uint32((b | (bits << availableBits)) & bitMask) + baseValue;

	    bits >>= (bitCount - availableBits);
		availableBits += NumberUtil::UINT64_BITS - bitCount;
	}
}

inline bool Index::Iterator::skip() {
	while (true) {
		if (--remainingCount == 0) {
			if (!nextChunk()) {
				return false;
			}
		}

		fetchValue();
		valueIndex++;

		if (rangeMin <= value && value <= rangeMax) {
			return true;
		}
	}
}

inline bool Index::Iterator::skip(uint skipCount) {
	if (remainingCount == 0) {
		return false;
	}

	if (skipCount == 0) {
		return true;
	}

	if (--remainingCount == 0) {
		if (!nextChunk()) {
			return false;
		}
	}

	if (skipCount > 1) {
		skipCount--;

		while (skipCount >= remainingCount) {
			skipCount -= remainingCount;
			valueIndex += remainingCount;
			remainingCount = 0;

			uint prevValueIndex = valueIndex;
			if (!nextChunk()) {
				return false;
			}
			skipCount -= min(skipCount, valueIndex - prevValueIndex);
		}
	    
		uint skipBitCount = skipCount * bitCount;
		if (skipBitCount >= availableBits) {
			skipBitCount -= availableBits;
	    
			uint k = skipBitCount / (NumberUtil::UINT64_BITS);
			payload += k;
			skipBitCount -= k * NumberUtil::UINT64_BITS;
		
			bits = *payload++;
			availableBits = NumberUtil::UINT64_BITS;
		}
		
		bits >>= skipBitCount;
		availableBits -= skipBitCount;
		remainingCount -= skipCount;
		valueIndex += skipCount;
	}

	fetchValue();
	valueIndex++;

	if (rangeMin <= value && value <= rangeMax) {
		return true;
	}

	return skip();
}
